package test.tree;

public class BinaryTree {
	
	private TreeNode root;
	
	public TreeNode getRoot() {
		return root;
	}

	public void setRoot(TreeNode root) {
		this.root = root;
	}
	
	public void add(int...datas) {
		for(int data : datas) {
			add(data);
		}
	}
	
	public void add(int data) {
		add(data, root);
	}
	
	
	/**5
	 * 				3
	 * 		1				6
	 * 					4
	 * 
	 * 3->6->4
	 * 
	 * @param data
	 * @param node
	 * @param parent
	 */
	private void add(int data, TreeNode node) {
		
		if(node==null) { 
			root = new TreeNode(); 
			root.setData(data); 
			return;
		}
		
		int tempData = node.data;
		TreeNode left = node.left;
		TreeNode right = node.right;
		if(data < tempData) {
			if(left==null) {
				TreeNode addNode = new TreeNode();
				addNode.data = data;
				addNode.isLeftChild = true;
				addNode.parent = node;
				node.left = addNode;
			} else {
				add(data, left);
			}
		} else if(data > tempData) {
			if(right==null) {
				TreeNode addNode = new TreeNode();
				addNode.data = data;
				addNode.isLeftChild = false;
				addNode.parent = node;
				node.right = addNode;
			} else {
				add(data, right);
			}
		} else {
			throw new RuntimeException("已存在同样的节点");
		}
	}
	
	private TreeNode search(int data, TreeNode node) {
		if(node==null) {
			return null;
		}
		
		int tempData = node.data;
		if(data < tempData) {
			return search(data, node.left);
		} else if(data > tempData) {
			return search(data, node.right);
		} else {
			return node;
		}
	}
	
	public TreeNode search(int data) {
		TreeNode node = search(data, root);
		return node;
	}
	
	private TreeNode forSearch(int data, TreeNode node) {
		for(;;) {
			if(node==null) {
				return null;
			}
			int tempData = node.data;
			if(data < tempData) {
				node = node.left;
			} else if(data > tempData) {
				node = node.right;
			} else {
				return node;
			}
		}
	}
	
	public TreeNode forSearch(int data) {
		return forSearch(data, root);
	}
	
	public void delete(int data) {
		TreeNode node = search(data);
		
		if(node.left!=null && node.right!=null) {
			TreeNode temp = successor(node);
			node.data = temp.data;
			node = temp;
		}
		
		TreeNode parent = node.parent;
		TreeNode child = null;
		if(node.left!=null) {
			child = node.left;
		} else if(node.right!=null) {
			child = node.right;
		}
		
		if(child!=null) {
			child.parent = parent;
		}
		if(node.isLeftChild) {
			parent.left = child;
		} else {
			parent.right = child;
		}
	}
	
	/**
	 * 获取node下最小节点
	 * @param node
	 * @return
	 */
	private TreeNode min(TreeNode node) {
		while(node.left!=null) {
			node = node.left;
		}
		TreeNode min = node;
		return min;
	}
	
	/**
	 * 后继节点
	 * @param node
	 * @return
	 */
	private TreeNode successor(TreeNode node) {
		// 如果node存在右孩子，则"node的后继结点"为 "以其右孩子为根的子树的最小结点"。
		if(node.right!=null) {
			return min(node.right);
		}
		
		//如果node不存在右孩子
		//1 如果该节点为左孩子，后继节点就是他的父节点
		//2 如果该节点为右孩子，往上去找他的父节点，直到找到一个是左孩子的父节点，这个父节点的父节点就是后继节点
		if(node.isLeftChild) {
			return node.parent;
		} else {
			while(!node.parent.isLeftChild) {
				node = node.parent;
			}
			return node.parent.parent;
		}
	}
	
	/**
	 * 前驱节点
	 * @param node
	 * @return
	 */
	private TreeNode precursor(TreeNode node) {
		return null;
	}
	
	public static void main(String[] args) {
		BinaryTree bt = new BinaryTree();
		bt.add(50, 30, 80, 20, 35, 34, 32, 40, 70, 75, 100);
		System.out.println(bt.root);
		
		/**
		 * 					50
		 *             / 		\
		 * 	   30					80
		 * 	  /   \                /   \
		 * 20		35          70      100
		 * 	       /  \           \
		 * 		  34   40          75
		 *		 /
		 *		32 
		 * 
		 */
		
		TreeNode node = bt.forSearch(40);
		
		System.out.println(node);
//		
//		System.out.println("parent=" + node.parent);
//		System.out.println("left=" + node.left);
//		System.out.println("right=" + node.right);
		
		bt.delete(35);
		TreeNode node32 = bt.search(40);
		System.out.println(node32);
		System.out.println(node32.left);
		System.out.println(node32.right);
		
//		TreeNode node = bt.search(50);
//		node = bt.successor(node);
//		System.out.println(node);
	}
	
	static class TreeNode {
		
		private int data;
		private boolean isLeftChild;
		private TreeNode parent;
		private TreeNode left;
		private TreeNode right;
		public int getData() {
			return data;
		}
		public void setData(int data) {
			this.data = data;
		}
		public TreeNode getLeft() {
			return left;
		}
		public void setLeft(TreeNode left) {
			this.left = left;
		}
		public TreeNode getRight() {
			return right;
		}
		public void setRight(TreeNode right) {
			this.right = right;
		}
		public TreeNode getParent() {
			return parent;
		}
		public void setParent(TreeNode parent) {
			this.parent = parent;
		}
		public boolean isLeftChild() {
			return isLeftChild;
		}
		public void setLeftChild(boolean isLeftChild) {
			this.isLeftChild = isLeftChild;
		}
		@Override
		public String toString() {
			return "TreeNode [data=" + data + ", left=" + (left==null?null:left.data) + ", right=" + (right==null?null:right.data) + ", parent=" + (parent==null?null:parent.data) + "]";
		}
	}

}